백준 11438번

오늘 풀어본 문제는 백준의 11438번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N$ $(2 \leq N \leq 100,000)$개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 $1$번부터 $N$번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 $M$ $(1 \leq M \leq 100,000)$개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 $N$이 주어지고, 다음 $N-1$개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 $M$이 주어지고, 다음 $M$개 줄에는 정점 쌍이 주어진다.

출력

$M$개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

풀이과정

첫 번째 시도

이 문제는 최소 공통 조상 (LCA) 을 찾는 문제이다. 그냥 단순히 부모 노드를 방문하면서 일치하는 게 나올 때까지 비교해도 가능은 하겠지만, 한 쌍에 대해서만 LCA를 찾는 문제가 아니라, 여러 개의 노드 쌍에 대해서 찾아야 하기 때문에, 이러한 방식은 시간초과를 발생시킬 수 있다. 그래서 방금 같은 방법 대신 Sparse Table 이라는 것을 이용해서 풀어야 하는 문제이다.

원리를 간단하게 설명하자면 다음과 같다. 어떤 노드의 부모 노드를 $1$차 부모 노드, 어떤 노드의 부모 노드의 부모 노드를 $2$차 부모 노드, 부모의 부모의 부모 노드를 $3$차 부모 노드, 이런 식으로 정의해보자.

우선 모든 노드에 대해 $1$차 부모, $2$차 부모, $4$차 부모, $8$차 부모 등 $2^n$차 부모들을 저장해둔다. 이 정보를 가지고 우리는 LCA을 찾아낼 것이다.

그 다음은, 어떤 두 노드를 입력받는다. 우선 이 두 노드의 깊이를 알아낸 뒤, 그 두 노드의 높이를 맞춰준다. 이 높이를 맞추는 과정에서, 높이의 차이만큼 그대로 올려주는 대신, 우리가 저장해둔 정보를 이용하여 높이를 맞춰줄 수 있다.

예를 들어, 높이의 차이가 $10$ 이라고 하면, 부모 노드에 $10$번 접근하는 대신, $10 = 8 + 2$ 라는 점을 이용하여 $8$차 부모에 한번 접근하고, 그 다음 $2$차 부모에 접근하는 식이다. 모든 자연수는 이런 식으로 $2^n$ 들의 합으로 나타낼 수 있기 때문에 가능한 방법이다.

높이를 맞춘 뒤, 만약 둘이 같다면, 그게 바로 LCA가 된다. 그렇지 않은 경우, 본격적으로 LCA를 찾는 과정이 시작된다.

여기서 한 가지 기억해야 할 사실은, 우리가 찾는 것은 그냥 공통 조상이 아니라, ‘최소 공통 조상’ 이라는 점이다. 무턱대고 높이 올라갔다가는, 최소가 아니게 될 수 있다는 의미이다. 그래서 우리는 최소 공통 조상의 ‘직전’까지 올라간 뒤, 마지막으로 그 직전의 부모에 접근하는 방식으로 LCA를 찾아낼 것이다. 올라가는 과정은, $2^n$ 차 부모에 계속해서 접근하는데 $n$이 큰 것부터 접근을 시도해나가는 것이다.

여기서, 그 ‘직전’의 부모가 LCA인 이유는, 각각의 노드에서 올라간 부모가 같지 않은 상태에서 최대한으로 올라가기 때문에, 한 칸 더 올라가면 LCA가 나오는 것이다. 예를 들어, $10$ 칸을 더 올라가야 LCA가 나온다고 하면, $9$ 칸만 올라간 뒤, $1$ 칸을 더 올라가면 도착하는 것이다. (참고로 실제 코드가 작동하는 과정에서는 올라가야 하는 칸이 정확히 몇 칸인지는 알 수 없으나, 정확히 몇 칸인지는 몰라도 된다.)

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> tree(100001);

int depth[100001] = { 0, };
int parent[100001][18] = { 0, };
bool visited[100001] = { 0, };

void setImmediateParent(int currentNode, int currentDepth);
void setParentDP(int N);
int findLCA(int nodeA, int nodeB);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, nodeA, nodeB;

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		cin >> nodeA >> nodeB;

		tree[nodeA].emplace_back(nodeB);
		tree[nodeB].emplace_back(nodeA);
	}

	setImmediateParent(1, 0);
	setParentDP(N);

	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> nodeA >> nodeB;
		cout << findLCA(nodeA, nodeB) << "\n";
	}

	return 0;
}

void setImmediateParent(int currentNode, int currentDepth) {
	visited[currentNode] = true;
	depth[currentNode] = currentDepth;

	for (auto i : tree[currentNode]) {
		if (visited[i] == false) {
			parent[i][0] = currentNode;
			setImmediateParent(i, currentDepth + 1);
		}
	}
}

void setParentDP(int N) {
	int maximumHeight = 0;
	
	for (int tempN = N; tempN > 1; maximumHeight++) {
		tempN >>= 1;
	}

	for (int i = 1; i <= maximumHeight; i++) {
		for (int j = 1; j <= N; j++) {
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
		}
	}
}

int findLCA(int nodeA, int nodeB) {
	if (depth[nodeA] < depth[nodeB]) {
		swap(nodeA, nodeB);
	}

	int difference = depth[nodeA] - depth[nodeB];
	int power = 0;

	while (difference > 0) {
		if (difference % 2 == 1) {
			nodeA = parent[nodeA][power];
		}
		difference = difference >> 1;
		power++;
	}

	if (nodeA == nodeB) {
		return nodeA;
	}
	else {
		for (int i = 17; i >= 0; i--) {
			if (parent[nodeA][i] != 0 && parent[nodeA][i] != parent[nodeB][i]) {
				nodeA = parent[nodeA][i];
				nodeB = parent[nodeB][i];
			}
		}

		return parent[nodeA][0];
	}
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

이번 글을 읽고 많은 의문점이 드는 사람들이 있을 수 있다. 하나씩 답변해보도록 하겠다.

1. 왜 갑자기 CLASS 6 문제를 풀게 되었나요?

   갑자기 CLASS 6 문제를 푼 것은 아니고, 풀어본 문제가 CLASS 6이었던 것이다. 포항에 내려온 뒤로, 나는 알고리즘 동아리에서 세미나를 듣고 있고, 다룬 내용 중 하나가 LCA가 있었으며, 연습 문제로 제공된 문제가 이 문제이다.

   어짜피 매일 PS도 하고 글도 올리는 겸, 주제를 이 문제로 잡아보았다. 사실 이 문제를 풀기 시작한 것은 며칠되었다. 요즘은 계속 CLASS 4 문제를 풀다가 갑자기 그제 CLASS 3 풀었는데, 아마 그 날이 풀기 시작했던 날일 것이다.

2. 오늘따라 풀이가 왜 이리 길고 장황한가요?

   문제를 푸는데 필요한 내용이 많고 복잡했는데, 글을 쓰면서 다 생략을 해버리기엔 너무 성의가 없는 것 같아서 풀이를 작성해두었다. 이 프로젝트가 알고리즘에 대한 설명을 깔끔하게 정리하는 것이 목표는 아니지만, 관련된 내용을 아예 설명하지 않고 답만 딸랑 쓰기도 애매했기 때문에 적었던 것이다.

   그리고 오늘따라 뭔가 영 피곤하다. 솔직히 내가 글을 쓰면서도 말을 너무 복잡하게 쓴다는 것 정도는 스스로 느낄 수 있었다. 내가 정리한 것 보다 더 깔끔하게 잘 정리한 사람들이 많으니 만약 이 설명이 이해가 잘 안 간다면 그런 글들을 참고해주길 바란다.

3. 도대체 해석학 게임 만들기 프로젝트는 어떻게 된건가요?

   망했다. 포항에 내려오고서 본격적으로 ‘의무적으로’ 해야할 일들이 생기면서, 그런 일들을 처리하다 보니 점점 해석학 공부를 하여 내용을 정리하는데 어려움을 겪고 있다. 빠른 시일내에 원상복귀하도록 노력하곘다. 좀만 참고 기다려주길 바란다. 현 시점에서는 아무도 기다리지 않겠지만 말이다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/11438